/*
 * @lc app=leetcode.cn id=785 lang=cpp
 *
 * [785] 判断二分图
 */

#include <limits.h>

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

// @lc code=start
class Solution {
   public:
    bool isBipartite(vector<vector<int>>& graph) {
        int count = 0;
        int length = graph.size();      // 统计节点数量
        vector<int> color(length, -1);  // 记录节点和颜色的映射关系
        queue<int> nodes;               // 记录 BFS 待访问的节点

        while (count < length) {
            // 找一个新的未染色的节点
            for (int i = 0; i < length; i++) {
                if (color[i] == -1) {
                    nodes.push(i);
                    color[i] = 0;
                    break;
                }
            }

            // BFS
            while (!nodes.empty()) {
                int curNode = nodes.front();
                int curColor = color[curNode];
                nodes.pop();
                count++;

                for (int node : graph[curNode]) {
                    // 邻居节点尚未访问
                    if (color[node] == -1) {
                        nodes.push(node);            // 加入等待队列
                        color[node] = 1 - curColor;  // 染色
                    }

                    // 邻居节点已有相同颜色，直接返回 false
                    if (color[node] == curColor) return false;
                }
            }
        }

        return true;
    }
};
// @lc code=end
